package JZ_Offer.algorithm.other.贪心;

/**
 * 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 * 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 */
public class JZ45_把数组排成最小的数 {

    /**
     * 比较两个字符串s1, s2大小的时候，先将它们拼接起来，比较s1+s2,和s2+s1那个大，
     * 如果s1+s2大，那说明s2应该放前面，所以按这个规则，s2就应该排在s1前面。
     */
    public static String PrintMinNumber(int[] numbers) {
        for (int i = numbers.length; i > 0; i--) {
            for (int j = 0; j < i - 1; j++) {
                compareAndSwap(numbers, j, j + 1);
            }
        }
        return toString(numbers);
    }

    private static void compareAndSwap(int[] n, int i, int j) {
        Long ab = Long.valueOf(n[i] + "" + n[j]);
        Long ba = Long.valueOf(n[j] + "" + n[i]);
        if (ab > ba) {
            n[i] = n[i] ^ n[j];
            n[j] = n[i] ^ n[j];
            n[i] = n[i] ^ n[j];
        }
    }

    private static String toString(int[] numbers) {
        StringBuilder b = new StringBuilder();
        for (int number : numbers) {
            b.append(number);
        }
        return b.toString();
    }

    public static void main(String[] args) {
        int[] numbers = new int[]{3334, 3, 3333332};
        System.out.println(PrintMinNumber(numbers));
    }
}
